import java.util.*;


interface Sorter {
	void sort( Comparable [ ] a );
}


class MergeSort implements Sorter {

	public void sort( Comparable [ ] a ) {
		Comparable [ ] tmp = new Comparable[ a.length ];
		sort( a, tmp, 0, a.length - 1 );
	}

	void sort( Comparable [ ] a, Comparable [ ] tmp, int left, int right) {
		if ( left < right ) {
			int center = ( left + right ) / 2;
			sort( a, tmp, left, center );
			sort( a, tmp, center + 1, right );
			merge( a, tmp, left, center, center + 1, right );
		}
	}

	void merge( Comparable [ ] a, Comparable [ ] tmp,
				int leftStart, int leftEnd,
				int rightStart, int rightEnd) {

		int leftPos = leftStart;
		int rightPos = rightStart;
		int tmpPos = leftStart;

		while ( leftPos <= leftEnd && rightPos <= rightEnd ) {
			if ( a[ leftPos ].compareTo( a[ rightPos ] ) < 0 ) {
				tmp[ tmpPos++ ] = a[ leftPos++ ];
			}
			else {
				tmp[ tmpPos++ ] = a[ rightPos++ ];
			}
		}

		while ( leftPos <= leftEnd ) {
			tmp[ tmpPos++ ] = a[ leftPos++ ];
		}

		while ( rightPos <= rightEnd ) {
			tmp[ tmpPos++ ] = a[ rightPos++ ];
		}

		for ( int i = leftStart; i <= rightEnd; ++i ) {
			a[ i ] = tmp[ i ];
		}
	}
}


class InsertionSort implements Sorter {

    public void sort( Comparable [ ] a ) {

        for( int p = 1; p < a.length; p++ ) {
            Comparable tmp = a[ p ];
			
            int j;
            for(j = p ; j > 0 && tmp.compareTo( a[ j - 1 ] ) < 0; j-- ) {
                a[ j ] = a[ j - 1 ];
			}

            a[ j ] = tmp;
        }
    }
}


class SelectionSort implements Sorter {

    public void sort (Comparable[] a) {

		for (int i = 0; i < a.length-1; i++) {
	    	int min = i;

	    	for (int j = i+1; j < a.length; j++) {

				if (a[j].compareTo(a[min]) < 0) {
		    		min = j;
				}
			}

	    	Comparable tmp = a[min];
	    	a[min] = a[i];
	    	a[i] = tmp;
		}
    }
}


public class Sort {

	static void runSort(Sorter sorter, String sortName) {

		System.out.println(sortName);

		for (int SIZE = 100; SIZE < 1000000; SIZE *= 2) {
	    	long start, end;
	    	long elapsed1 = 0, elapsed2 = 0, elapsed3 = 0;
	    	Comparable [ ] a = new Comparable [ SIZE ];

			// sorted input
	    	for( int i = 0; i < SIZE; i++ ) {
				a[ i ] = new Integer( i );
			}
	    	start = System.currentTimeMillis();
	    	sorter.sort( a );
	    	end = System.currentTimeMillis();
	    	elapsed1 = end - start;

			// reverse sorted input
		    for( int i = 0; i < SIZE; i++ ) {
				a[ i ] = new Integer( SIZE - i );
			}
	    	start = System.currentTimeMillis();
	    	sorter.sort( a );
	    	end = System.currentTimeMillis();
	    	elapsed2 = end - start;

			// random input
		    Random r = new Random();
		    for( int i = 0; i < SIZE; i++ ) {
				a[ i ] = new Integer( r.nextInt(SIZE) );
			}
		    start = System.currentTimeMillis();
		    sorter.sort( a );
	    	end = System.currentTimeMillis();
		    elapsed3 = end - start;

		    System.out.println("size: " + SIZE + 
							   "\tsorted: " + elapsed1 + 
						       "\treverse: " + elapsed2 + 
							   "\trandom: " + elapsed3);
		}
	}

    public static void main (String[] args) {
		runSort(new MergeSort(), "Merge Sort");
		runSort(new InsertionSort(), "Insertion Sort");
		runSort(new SelectionSort(), "Selection Sort");
    }

}